package a08_回溯算法;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * <p>
 * a05_电话号码的字母组合复习1
 * </p>
 *
 * @author flyduck
 * @since 2024/12/31
 */
public class a05_电话号码的字母组合复习1 {

    public static void main(String[] args) {
        a05_电话号码的字母组合复习1 test = new a05_电话号码的字母组合复习1();
        test.letterCombinations("23");
    }

    public List<String> letterCombinations(String digits) {
        String[] dictArray = new String[]{
                "",
                "",
                "abc",
                "def",
                "ghi",
                "jkl",
                "mno",
                "pqrs",
                "tuv",
                "wxyz",
        };
        char[] digitsCharArray = digits.toCharArray();
        int[] digitsArray = new int[digitsCharArray.length];
        for (int i = 0; i < digitsCharArray.length; i++) {
            digitsArray[i] = Integer.valueOf(new Character(digitsCharArray[i]).toString());
        }

        List<String> result = new ArrayList<>();
        LinkedList<Character> path = new LinkedList<>();
        if (digits == null || "".equals(digits)) {
            return result;
        }
        traversal(dictArray,result,path,digitsArray,0 );
        return result;

    }

    private void traversal(String[] dictArray,
                           List<String> result,
                           LinkedList<Character> path,
                           int[] digitsArray,
                           int digitsArrayIdx){
        if(path.size() == digitsArray.length){
            String collect = path.stream().map(c -> c.toString()).collect(Collectors.joining(""));
            result.add(collect);
            return;
        }
        char[] chars = dictArray[digitsArray[digitsArrayIdx]].toCharArray();
        for (int i = 0; i < chars.length; i++) {
            path.add(chars[i]);
            traversal(dictArray, result, path, digitsArray, digitsArrayIdx + 1);
            path.removeLast();
        }
    }
}
